package com.leetcode.题库;

/**
 * @author 覃国强
 * @date 2022-02-28 14:28
 */
public class 题库_1601_最多可达成的换楼请求数目 {

  static
  class Solution {
    public int maximumRequests(int n, int[][] requests) {
      return maxRequests(n, requests, 0, new int[n], n, 0);
    }

    private int maxRequests(int n, int[][] requests, int index, int[] variety, int zeroCount, int curAnswer) {
      if (index == requests.length) {
        return zeroCount == n ? curAnswer : 0;
      }

      // 不要当前请求
      int answer1 = maxRequests(n, requests, index + 1, variety, zeroCount, curAnswer);

      // 要当前请求
      int from = requests[index][0];
      int to = requests[index][1];

      zeroCount -= (variety[from] == 0 ? 1 : 0);
      variety[from] -= 1;
      zeroCount += (variety[from] == 0 ? 1 : 0);

      zeroCount -= (variety[to] == 0 ? 1 : 0);
      variety[to] += 1;
      zeroCount += (variety[to] == 0 ? 1 : 0);

      int answer2 = maxRequests(n, requests, index + 1, variety, zeroCount, curAnswer + 1);

      // 恢复
      variety[from] += 1;
      variety[to] -= 1;

      return Math.max(answer1, answer2);
    }

  }

}
